package com.estar.integaration.Util;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * Author: YJL
 * Date: 2022/1/4 11:04
 **/
public class Solution {
  static List<List<Integer>> ans = new ArrayList<List<Integer>>();
  static Deque<Integer> stack = new ArrayDeque<Integer>();

  public static List<List<Integer>> allPathsSourceTarget(Integer[][] graph) {
    stack.offerLast(0);
    dfs(graph, 0, graph.length - 1);
    return ans;
  }

  public static void dfs(Integer[][] graph, int x, int n) {
    if (x == n) {
      ans.add(new ArrayList<Integer>(stack));
      return;
    }
    for (int y : graph[x]) {
      stack.offerLast(y);
      dfs(graph, y, n);
      stack.pollLast();
    }
  }
}
